/*
 * @Author: guojiangang guojiangang@hikvision.com.cn
 * @Date: 2024-02-27 16:36:37
 * @LastEditors: guojiangang guojiangang@hikvision.com.cn
 * @LastEditTime: 2024-02-27 17:08:06
 * @FilePath: \cfase:\leetcode\21.合并两个有序链表.js
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=21 lang=javascript
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
// 递归
var mergeTwoLists = function(list1, list2) {
  if (list1 === null) return list2
  if (list2 === null) return list1
  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2)
    return list1
  }
  list2.next = mergeTwoLists(list2.next, list1)
  return list2
};
/* 
list1 = [1,2,4]
list2 = [1,3,4]

第1次进入mergeTwoLists方法
list1 = [1,2,4]
list2 = [1,3,4]
走到list2.next = mergeTwoLists(list2.next, list1)
list2 = [1, ...mergeTwoLists([3, 4], [1, 2, 4])]
返回list2

第2次进入mergeTwoLists方法
list1 = [3, 4]
list2 = [1, 2, 4]
走到list1.val < list2.val
list1.next = mergeTwoLists(list1.next, list2)
list1 = [1, ...mergeTwoLists([2, 4], [3, 4])]
返回list1

第3次进入mergeTwoLists方法
list1 = [2, 4]
list2 = [3, 4]
走到list1.val < list2.val
list1.next = mergeTwoLists(list1.next, list2)
list1 = [2, ...mergeTwoLists([4], [3, 4])]
返回list1


第4次进入mergeTwoLists方法
list1 = [4]
list2 = [3, 4]
走到list2.next = mergeTwoLists(list2.next, list1)
list2 = [3, ...mergeTwoLists([4], [4])]
返回list2

第5次进入mergeTwoLists方法
list1 = [4]
list2 = [4]
走到list2.next = mergeTwoLists(list2.next, list1)
list2 = [4, ...mergeTwoLists(null, [4])]
返回list2

第6次进入mergeTwoLists方法
list1 = null
list2 = [4]
返回list2
*/

// 迭代
var mergeTwoLists = function(list1, list2) {
  const prehead = new ListNode(-1)

  let prev = prehead
  while (list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      // prev.next改变了prehead.next也会改变
      prev.next = list1
      list1 = list1.next
    } else {
      prev.next = list2
      list2 = list2.next
    }
    prev = prev.next
  }
  prev.next = list1 === null ? list2 : list1
  return prehead
};

// @lc code=end

